<?php
/**
 * Given an array A of integers, find the maximum of j-i subjected to the constraint of
 * A[i] < A[j].
 */
require_once 'util.php';

$sample = generateRandomArray(1, 10, 10);

echo implode( ' ', $sample );

echo "<br/>";

distance_maximize($sample);

echo "<br/>";

distance_maximize_awesome($sample);

// Look for the max distance
// Algo 1 is the stupid method, loop through all
function distance_maximize( $sample ){
	$size = count($sample);
	if( $size <= 0 ){
		return null;
	}
	
	$max_diff = 0;
	// Two index b-a is max subjected to A[a]<A[b]
	$a = 0;
	$b = 0;
	for( $i=0; $i<$size-1; $i++ ){
		for( $j=$i+1; $j<$size; $j++ ){
			
			// Skipping equal elements
			if( $sample[$i] >= $sample[$j] ){
				continue;
			}
			else {
				$diff = $j - $i;
				if( $diff > $max_diff ){
					$a = $i;
					$b = $j;
					$max_diff = $diff;
				}
			}
			
		}
	}
	
	echo "$b - $a is the max difference.<br/>";
}

// Algo 2: The smart solution
// We only want to try the possible combinations:
// A[j] that is larger than A[j+1] to A[n-1] (RMax)
// A[i] that is smaller than A[0] to A[i-1] (LMin)
function distance_maximize_awesome( $sample ){
	$size = count( $sample );
	if( 0 >= $size ){
		return null;
	}
	
	$RMax = array_fill(0, $size, 0);
	$RMax[$size-1] = $sample[$size-1];
	// Construct the RMax array
	for( $j=$size-2; $j>=0; $j-- ){
		$RMax[$j] = max($sample[$j], $RMax[$j+1]);
	}
	
	// LMin was supposed to be an array similar to RMax but 
	// since we will traverse left to right, it can be just 
	// a humble variable to save space.
	$LMin = $sample[0];
	
	$i = 0;
	$j = 1;
	$diff = 0;
	$a = 0;
	$b = 0;
	while( $i < $size && $j < $size ){
		$LMin = min( $LMin, $sample[$i] );
		if( $LMin < $RMax[$j] ){
			if( ($j - $i) > $diff ){
				// A new record
				$a = $i;
				$b = $j;
				$diff = $j - $i;
			}
			// j can do better!
			// Apparently we are skipping same RMax values but actually
			// we are skipping A[j] values not in our interest.
			$j++;
		}
		else {
			// i too low, increment i
			// Same as above, we are moving to the right for a lower A[i] value that
			// hopefully can have better A[j] match to the right
			$i++;
		}
	}
	
	echo "$b - $a is the max difference.<br/>";
	
}